Logic devices such as FPGAs and structured ASICs are used to implement large systems that include million of gates and megabits of embedded memory. The complexity of large systems often requires the use of EDA tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) flow are synthesis, mapping, placement, and routing.
Iterative improvement is one technique that may be used for performing placement by EDA tools. Iterative improvement generates an initial placement solution and evolves the placement by making changes to a subset of the solutions. Simulated annealing is one of several iterative improvement algorithms that are commonly used. Analytic placement is a technique that is more commonly used for performing placement on ASICs. Analytic placement establishes a formula that can be used to compute the cost for a potential placement. The formula may include one or more equations. The formula may take into account cost components such as the amount of wire needed to connect together cells such as a logic-array block, register, memory, or other component, the speed of the resulting design, the amount of power used, or other criteria. Cells may be assigned to the locations on the ASIC by considering solutions which maximize or minimize an objective. Quadratic placement is one of several analytic placement algorithms that are commonly used.
Analytic placement techniques are faster than iterative improvement techniques, but their applications traditionally have been limited to ASICs since analytic placement techniques have significant trouble with restricted areas on FPGAs and structured ASICs. Modern FPGAs and structured ASICs have restricted areas where only certain classification of cells may be placed. For example, FPGAs and structured ASICs have pre-fabricated locations that can only be used to implement RAMs or multipliers and cannot be used for other elements such as logic-array blocks. These restrictive areas may be scattered across a device in a regular or irregular manner.